package com.lw.leetcode.stack.c;

import java.util.Stack;

/**
 * 84. 柱状图中最大的矩形
 *
 * @Author liw
 * @Date 2021/6/16 17:29
 * @Version 1.0
 */
public class LargestRectangleArea {

    public static void main(String[] args) {
        LargestRectangleArea test = new LargestRectangleArea();
        //        int[] arr = {2, 1, 5, 6, 2, 3};
//        int[] arr = {2,3,4,5,6};
//        int[] arr = {6,5,4,3,2};
//        int[] arr = {6};
        int[] arr = {1, 2, 6, 6, 1};
        int i = test.largestRectangleArea(arr);
        System.out.println(i);
    }

    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }
        int length = heights.length;
        Stack<Integer> index = new Stack<>();
        Stack<Integer> value = new Stack<>();
        int max = 0;
        index.add(-1);
        value.add(0);
        for (int i = 0; i < length; i++) {
            int v = heights[i];
            if (value.peek() > v) {
                Integer st = index.peek();
                while (value.peek() > v) {
                    int item = value.pop();
                    index.pop();
                    int l = st - index.peek();
                    max = Math.max(max, l * item);
                }
            }
            value.add(v);
            index.add(i);
        }
        if (!value.isEmpty()) {
            Integer st = index.peek();
            while (value.size() > 1) {
                int item = value.pop();
                index.pop();
                int l = st - index.peek();
                max = Math.max(max, l * item);
            }
        }
        return max;
    }
}
